#include<stdio.h>
#include<stdlib.h>
using namespace std;
void halfInsertSort(int a[],int n){
    int low,high,mid,i,j;
    int t;
    for(i=1;i<n;i++){//先把a[0]看成已经有序
        t=a[i];
        low=0;high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(a[mid]>t){//比较
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        // 找到了待插入的位置low
        j=i-1;
        while(j>=low){//该位置后面元素往后移
            a[j+1]=a[j];
            j--;
        }
        a[low]=t;//插入
    }

}
int main(){
    int a[5]={1,4,3,2,5};
    halfInsertSort(a,5);
    printf("%d%d%d%d%d",a[0],a[1],a[2],a[3],a[4]);
    return 0;
}